package oj;

import java.util.Deque;
import java.util.LinkedList;

//逆波兰表达式：根据 逆波兰表示法，求表达式的值。
//有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
//注意 两个整数之间的除法只保留整数部分。
//可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
public class Solution_150 {
    //判断是否为运算符
    private static boolean isOperator(String s){
        //String 比较用 equals()
        if(s.equals("+")){
            return true;
        }
        if(s.equals("-")){
            return true;
        }
        if(s.equals("*")){
            return true;
        }
        return s.equals("/");
    }

    //计算表达书
    private static long compute(long n1,long n2,String op){
        //Java 中的 swtich case 支持 String 类型
        switch (op){
            case "+": return n2 + n1;
            case "-": return n2 - n1;
            case "*": return n2 * n1;
            case "/": return n2 / n1;
            default: return -1;
        }
    }

    public static int evalRPN(String[] tokens) {
        //将数字入栈，遇到运算符就从栈中拿出两个元素进行计算，将运算结果继续入栈
        Deque<Long> stack = new LinkedList<>();
        //遍历字符串
        for(String token : tokens){
            if(!isOperator(token)){
                Long n = Long.parseLong(token);
                stack.push(n);
            }else{
                //由题可知，逆波兰表达式总是有效，所以在出栈的时候，栈中元素必有两个及两个以上
                long n1 = stack.pop();
                long n2 = stack.pop();
                long r = compute(n1,n2,token);
                stack.push(r);
            }
        }
        long e = stack.pop();
        return (int)e;
    }

    public static void main(String[] args) {
        String[] token = {"1","2","+","3","*","6","-"};
        System.out.println(evalRPN(token));
    }
}
